#ifndef BIGINT_H
#define BIGINT_H

#include <iostream>
#include <sstream>
#include <vector>
#include <string>
#include <algorithm>
#include <cctype>

typedef long long digit_t;

class big_int_t
{
public:
   big_int_t();
   explicit big_int_t(unsigned long long digit);
   big_int_t(std::string str);

   bool operator<(const big_int_t& bigint) const;
   bool operator>(const big_int_t& bigint) const;
   bool operator<=(const big_int_t& bigint) const;
   bool operator>=(const big_int_t& bigint) const;
   bool operator==(const big_int_t& bigint) const;
   bool operator!=(const big_int_t& bigint) const;
   
   big_int_t& operator+=(const big_int_t& bigint);
   big_int_t& operator-=(const big_int_t& bigint);
   
   std::pair<big_int_t, big_int_t> divide_with_remainder(const big_int_t& bigint) const;

   big_int_t& operator<<=(int shift);
   big_int_t& operator>>=(int shift);

   big_int_t operator<<(int shift) const;
   big_int_t operator>>(int shift) const;

   friend std::istream& operator>>(std::istream &is, big_int_t &bigint);
   friend std::ostream& operator<<(std::ostream &os, const big_int_t &bigint);

   big_int_t& operator*=(digit_t digit);
   big_int_t operator*(digit_t digit) const;
private:
   static const digit_t BASE = 1000000000;
   static const unsigned int DIGIT_LENGTH = 9;

   int compare_to(const big_int_t& bigint) const;

   void normalize();

   digit_t find_short_divider(const big_int_t& bigint) const;
   void cut_zeroes();

   std::vector<digit_t> digits_;
   int shift_;
};

#endif

